package binarytree;
import java.util.*;

public class BinaryTree {
    static class TreeNode {
        public int val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用
        public TreeNode(int val) {
            this.val = val;
        }
    }
        //public TreeNode root;
    /**
     * 创建一棵二叉树返回这棵树的根结点
     * @return
     */
        public TreeNode createTree(){
            TreeNode A =new TreeNode(1);
            TreeNode B =new TreeNode(2);
            TreeNode C =new TreeNode(3);
            TreeNode D =new TreeNode(4);
            TreeNode E =new TreeNode(5);
            TreeNode F =new TreeNode(6);
            TreeNode G =new TreeNode(7);
            TreeNode H =new TreeNode(8);
            A.left=B;
            A.right=C;
            B.left=D;
            B.right=E;
            C.left=F;
            C.right=G;
            E.right=H;
            return A;
    }
    // 前序遍历
   public void preOrder(TreeNode root){
            if(root==null)
                return;
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
   /*
   遍历思路
   List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
            if(root==null)
            {
                return list;
            }
            list.add(root.val);
            preorderTraversal(root.left);
            preorderTraversal(root.right);
      return list;
    }*/
    /**
     * 子问题思路
     * @param root
     * @return
     */
   public List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> list = new ArrayList<>();
       if(root==null)return list;
       list.add(root.val);
       List<Integer> leftTree = preorderTraversal(root.left);
       list.addAll(leftTree);
       List<Integer> rightTree = preorderTraversal(root.right);
       list.addAll(rightTree);
        return list;
   }
   /**
   非递归实现前序遍历
    * @param root
    * @return
    */
   public List<Integer> preorderTraversalNor(TreeNode root){
       List<Integer> list = new ArrayList<>();
       if(root==null)
           return list;
       Stack<TreeNode> stack = new Stack<>();
       TreeNode cur=root;
       while (cur!=null||!stack.empty()){
           while (cur!=null){
               stack.push(cur);
               list.add(cur.val);
               cur=cur.left;
           }
           TreeNode top=stack.pop();
           cur=top.right;
       }
       return list;
   }
   // 中序遍历
   public void inOrder(TreeNode root){
            if(root==null)
                return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    /**
     * 子问题思路中序遍历
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null)return list;
        List<Integer> leftTree = inorderTraversal(root.left);
        list.addAll(leftTree);
        list.add(root.val);
        List<Integer> rightTree = inorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }

    /**
     * 非递归中序遍历
     * @param root
     * @return
     */
    public List<Integer> inorderTraversalNor(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null)
            return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur=root;
        while (cur!=null||!stack.empty()){
            while (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            list.add(top.val);
            cur=top.right;
        }
        return list;
    }
    // 后序遍历
    public void postOrder(TreeNode root){
            if(root==null)
                return;
            postOrder(root.left);
            postOrder(root.right);
        System.out.print(root.val+" ");
    }
    /**
     * 子问题思路后序遍历
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null)return list;
        List<Integer> leftTree = postorderTraversal(root.left);
        list.addAll(leftTree);
        List<Integer> rightTree = postorderTraversal(root.right);
        list.addAll(rightTree);
        list.add(root.val);
        return list;
    }

    /**
     * 非递归后序遍历
     * @param root
     * @return
     */
    public List<Integer> postorderTraversalNor(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null)
            return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while (cur!=null||!stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if (top.right == null||top.right==prev) {
                stack.pop();
                list.add(top.val);
                prev=top;//防止重复打印
            } else {
                cur = top.right;

            }
        }
        return list;

    }
    /**
     * 子问题的思路：获取树中节点的个数
     * @param root
     * @return
     */
    int size2(TreeNode root){
        if(root==null)
            return 0;
        return size2(root.left)+size2(root.right)+1;
    }
    /*int size(TreeNode root){
        int sum=0;
        if(root==null)
            return 0;
        sum++;
        sum=sum+size(root.left);
        sum=sum+size(root.right);
        return sum;
 }*/
   public static int nodeSize;
   /**
     * 遍历思路求树中节点的个数
     * @param root
     */
   void size(TreeNode root){
        if(root==null)
            return;
        nodeSize++;
        size(root.left);
        size(root.right);
    }
    /**
     * 遍历思路：获取叶子节点的个数
     * @param root
     * @return
     */
    public static int leafSize = 0;
    void getLeafNodeCount1(TreeNode root){
        if(root==null)
            return;
        if(root.left==null&&root.right==null){
            leafSize++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
    }
   /* int getLeafNodeCount1(TreeNode root){
        int sum=0;
        if(root==null)
            return 0;
        if(root.right==null&&root.left==null)
            sum++;
        sum=sum+getLeafNodeCount1(root.left);
        sum=sum+getLeafNodeCount1(root.right);
        return sum;
    }
*/
    /**
     * 子问题思路：获取叶子节点的个数
     * @param root
     * @return
     */
   int getLeafNodeCount2(TreeNode root){
       if(root==null)
           return 0;
       if(root.left==null&&root.right==null)
          return 1;
       return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
   }
    /**
     *  获取第K层节点的个数
     * @param root
     * @return
     */
    int getKLevelNodeCount(int k,TreeNode root){
        if(root==null)
            return 0;
        if(k==1)
            return 1;
        return getKLevelNodeCount(k-1,root.left)+getKLevelNodeCount(k-1,root.right);
    }
    /**
     * 获取二叉树的高度
     * 时间复杂度：O(n)
     * 因为每个节点都要求高度，一共有n个结点所以是O(n)
     * @param root
     * @return
     */
    int getHeight(TreeNode root){
        if(root==null)
            return 0;
        int leftH=getHeight(root.left);
        int rightH=getHeight(root.right);
        return leftH>rightH?leftH+1:rightH+1;
        /*
        如果没有用leftH,rightH存的的是存储的话直接用
        return getHeight(root.left)>getHeight(root.right)?getHeight(root.left)+1:getHeight(root.right)+1;
        会因为递归次数太多oj超出时间限制
        */
    }
    /**
     * 检测值为value的元素是否存在
     * @param root
     * @param val
     * @return
     */
   TreeNode find(TreeNode root, int val){
       if (root==null)
           return null;
       if(root.val==val)
           return root;
      /* TreeNode l=find(root.left,val);
       TreeNode r=find(root.right,val);
       return (l!=null)?l:r;*/
       TreeNode ret = find(root.left,val);
       if(ret!=null){
           return ret;
       }
       ret=find(root.right,val);
       if(ret!=null){
           return ret;
       }
       return null;
   }
    /**
     * 非递归层序遍历
     * @param root
     */
    void levelOrder(TreeNode root){
        if(root==null)return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur=queue.peek();
            System.out.print(queue.poll().val+" ");
            if(cur.left!=null)
                queue.offer(cur.left);
            if(cur.right!=null)
                queue.offer(cur.right);
        }
    }
    /**
     * 非递归层序遍历以List<List<Integer>>方式存储
     * @param root
     */
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size!=0){
                TreeNode cur=queue.poll();
                list.add(cur.val);
                size--;
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            ret.add(list);
        }
        return ret;
    }
    /**
     * 判断一棵树是不是完全二叉树
     * @param root
     * @return
     */
    boolean isCompleteTree(TreeNode root){
        if(root==null)return false;
        Queue<TreeNode> queue= new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        //第2次遍历队列判断当中是否存在非空的元素
        while (!queue.isEmpty()){
            TreeNode cur = queue.peek();
            if(cur==null){
                queue.poll();
            }else {
                return false;
            }
        }
        return true;
       /* while (queue.peek()!=null){
            TreeNode cur = queue.poll();
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        queue.poll();
        int flag=0;
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur!=null){
                flag=1;
                break;
            }

        }
        if(flag==0)
            return true;
        else
            return false; //queue.offer(root);加这个写法也是正确的*/
    }
    /**
     * 判断两个二叉树是否相同
     * 时间复杂度：O(min(m,n))
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q!=null)
            return false;
        if(p!=null&&q==null)
            return false;
        if(p==null&&q==null)
            return true;
        if(p.val!=q.val)
            return false;
        return isSameTree(p.left,q.left)==true&&isSameTree(p.right,q.right)==true;

    }

    /**
     * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
     * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
     * 省流：是不是子树
     * 时间复杂度：O(t*s) root:t subRoot:s  子树需要跟root上的每个结点都要判断
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null)
            return false;
        if(isSameTree(root,subRoot))
            return true;
        if(isSubtree(root.left,subRoot))
            return true;
        if(isSubtree(root.right,subRoot))
            return true;
        return false;

    }

    /**
     * 判断是否是平衡树
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     * 本题中，一棵高度平衡二叉树定义为：
     * 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1
     * 时间复杂度是O(n*n)
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
       /* if(root==null)
            return true;

        if(Math.abs(getHeight(root.left)-getHeight(root.right))>1)
            return false;
        return isBalanced(root.left)&&isBalanced(root.right);*/
        if(root==null)
        return true;
        int leftH=getHeight(root.left);
        int rightH=getHeight(root.right);
        return Math.abs(leftH-rightH)<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }
    /**
     *  判断是否是平衡树
     *  时间复杂度是O(n)
     *  思路在求高度时顺便判断
     * @param root
     * @return
     */
    public int height(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftH = height(root.left);
        int rightH = height(root.right);
        if(leftH>=0&&rightH>=0&&Math.abs(leftH-rightH)<=1)
            return Math.max(rightH,leftH)+1;
        else
            return -1;
    }
    public boolean isBalanced1(TreeNode root) {
        if(root==null)
            return true;
        return height(root)>=0;

    }
    /**
     * 对称二叉树
     * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
     */
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
        if(leftTree==null&&rightTree!=null)
            return false;
        if(leftTree!=null&&rightTree==null)
            return false;
        if(leftTree==null&&rightTree==null)
            return true;
        if(leftTree.val!=rightTree.val)
            return false;
        return isSymmetricChild(leftTree.left,rightTree.right)&&isSymmetricChild(leftTree.right,rightTree.left);

    }
    public boolean isSymmetric(TreeNode root) {
        if(root==null)return true;
        return isSymmetricChild(root.left,root.right);
    }
    /**
     * 二叉树的最近公共祖先
     * 解法一：
     * 1.使用2个栈，存储从根节点到指定的节点的路径上的所有节点
     * 2.比较两个栈的大小，让栈中多的出差值个
     * 3.此时同时开始出栈，如果栈顶元素相同，那么此时这个值 就是最近公共祖先
     * 解法二：
     * 递归
     * 1.一个为根时，祖先为根
     * 2.两个值一个在左子树，一个在右子树，祖先为根
     * 3.都在左或都在右，最先遍历到的一定是
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //递归方法
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        //根不是，那么分别去找根的左边和根的右边
        TreeNode leftRet=lowestCommonAncestor(root.left,p,q);
        TreeNode rightRet=lowestCommonAncestor(root.right,p,q);
        if(leftRet!=null&&rightRet!=null){
            return root;
        }else if(leftRet!=null){
            return leftRet;
        }else if(rightRet!=null){
            return rightRet;
        }
        return null;

    }
     /**
    将指定结点node到root的路径上的节点存储到栈中
     */
     /*
    private boolean getPath(TreeNode root, TreeNode node,Stack<TreeNode> stack){
        if(root==null||node==null) return false;
        stack.push(root);
        if(root==node){
            return true;
        }
        boolean flg1= getPath(root.left,node,stack);
        if(flg1==true){
            return true;
        }
        boolean flg2= getPath(root.right,node,stack);
        if(flg2==true){
            return true;
        }
        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack1=new Stack<>();
        getPath(root,p,stack1);
        Stack<TreeNode> stack2=new Stack<>();
        getPath(root,q,stack2);
        int size1=stack1.size();
        int size2=stack2.size();
        if(size1>size2){
            int s=size1-size2;
            while(s!=0){
                stack1.pop();
                s--;
            }
        }else{
            int s=size2-size1;
            while(s!=0){
                stack2.pop();
                s--;
            }
        }
        while(!stack1.empty()&&!stack2.empty()){
            if(stack1.peek()==stack2.peek()){
                return stack1.peek();
            }else{
                stack1.pop();
                stack2.pop();
            }
        }
        return null;
    }
     */



}
